import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    int maxLen = 0;
    List<Integer> ans = new ArrayList<>();

    int prevVal = 10000000;
    int curLen = 0;

    public int[] findMode(TreeNode root) {
        inorder(root);

        int[] _ans = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            _ans[i] = ans.get(i);
        }
        return _ans;
    }

    void inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        inorder(root.left);

        if (prevVal != root.val) {
            curLen = 0;
        }
        curLen++;
        if (curLen >= maxLen) {
            if (curLen > maxLen) {
                maxLen = curLen;
                ans.clear();
            }
            ans.add(root.val);
        }
        prevVal = root.val;

        inorder(root.right);
    }
}

//迭代法
class Solution1 {
    public int[] findMode(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        int curLen = 0;
        int maxLen = 0;
        List<Integer> ans = new ArrayList<>();
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();

                if (prev == null || cur.val != prev.val) {
                    curLen = 0;
                }
                curLen++;
                if (curLen >= maxLen) {
                    if (curLen > maxLen) {
                        maxLen = curLen;
                        ans.clear();
                    }
                    ans.add(cur.val);
                }
                prev = cur;

                cur = cur.right;
            }
        }

        int[] mode = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            mode[i] = ans.get(i);
        }
        return mode;
    }
}